package com.veal98.tree;

import com.veal98.bean.TreeNode;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
import java.util.Stack;

public class FindModeInBinarySearchTree_501 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        // 2,1,3
        // 1,0,0
        // 3,0,0
        TreeNode root = createTree(sc);
        int[] res = findMode(root);
    }

    public static int[] findMode(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        // 辅助栈
        Stack<TreeNode> stack = new Stack<>();
        // 工作节点
        TreeNode cur = root;
        // 存储中序遍历的结果
        List<Integer> list = new ArrayList<>();

        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                // 左
                cur = cur.left;
            } else {
                // 根
                cur = stack.pop();
                list.add(cur.val);
                // 右
                cur = cur.right;
            }
        }


        // 先遍历一遍中序遍历序列，找出最多出现次数（maxCount）
        // 出现次数
        int count = 1;
        // 最多出现次数
        int maxCount = 1;
        for (int i = 0; i < list.size() - 1; i ++) {
            if (list.get(i).equals(list.get(i + 1))) {
                count ++;
                maxCount = Math.max(maxCount, count);
            } else {
                // 两者不相同 count 归 1
                count = 1;
            }
        }

        // 然后再重新遍历一遍中序遍历序列，把出现次数为 maxCount 的元素放进集合
        List<Integer> res = new ArrayList<>();
        list.add(Integer.MAX_VALUE);
        count = 1;
        for (int i = 0; i < list.size() - 1; i ++) {
            if (list.get(i).equals(list.get(i + 1))) {
                count ++;
            } else {
                count = 1;
            }

            if (count == maxCount) {
                res.add(list.get(i));
            }
        }


        int[] nums = new int[res.size()];
        int index = 0;
        for (int i : res) {
            nums[index ++] = i;
        }

        return nums;
    }

    public static int[] findMode2(TreeNode root) {
        if (root == null) {
            return new int[0];
        }

        // 辅助栈
        Stack<TreeNode> stack = new Stack<>();
        // 工作节点
        TreeNode cur = root;
        // 中序遍历的前驱节点
        TreeNode pre = null;
        // 存储众数
        List<Integer> res = new ArrayList<>();

        // 出现次数
        int count = 1;
        // 最多出现次数
        int maxCount = 1;

        while (!stack.isEmpty() || cur != null) {
            if (cur != null) {
                stack.push(cur);
                // 左
                cur = cur.left;
            } else {
                // 根
                cur = stack.pop();

                if (pre != null && pre.val == cur.val) {
                    count ++;
                } else {
                    // 与前驱节点数值不同
                    count = 1;
                }

                if (count == maxCount) {
                    res.add(cur.val);
                }
                if (count > maxCount) {
                    maxCount = count;
                    // 关键！清空 res
                    res.clear();
                    res.add(cur.val);
                }

                pre = cur;

                // 右
                cur = cur.right;
            }
        }

        // list 转数组
        return res.stream().mapToInt(Integer::intValue).toArray();
    }

    // 构造二叉树
    private static TreeNode createTree(Scanner sc) {
        String[] values = sc.nextLine().split(",");
        if (values.length < 3) {
            return null;
        }

        int value = Integer.parseInt(values[0]);
        int left = Integer.parseInt(values[1]);
        int right = Integer.parseInt(values[2]);

        TreeNode root = new TreeNode(value);
        if (left != 0) {
            root.left = createTree(sc);
        }
        if (right != 0) {
            root.right = createTree(sc);
        }

        return root;

    }

}
